# 依次遍历
# class Solution(object):
#     def getModifiedArray(self, length, updates):
#         """
#         :type length: int
#         :type updates: List[List[int]]
#         :rtype: List[int]
#         """
#         out = [0] * length
#         for item in updates:
#             for i in range(item[0], item[1] + 1):
#                 out[i] += item[2]
#         return out

import collections


class Solution(object):
    def getModifiedArray(self, length, updates):
        """
        :type length: int
        :type updates: List[List[int]]
        :rtype: List[int]
        """
        d_start = collections.defaultdict(int)
        d_end = collections.defaultdict(int)
        n = len(updates)
        starts = set()
        ends = set()
        out = [0] * length
        for i in range(n):
            start = updates[i][0]
            end = updates[i][1]
            d_start[start] += updates[i][2]
            d_end[end] += updates[i][2]
            starts.add(start)
            ends.add(end)
        starts = list(starts)
        starts.sort()
        n1 = len(starts)
        ends = list(ends)
        ends.sort()
        n2 = len(ends)
        prefix = 0
        cut_prefix = 0
        start_index = 0
        end_index = 0
        for i in range(length):
            if start_index < n1 and i == starts[start_index]:
                prefix += d_start[starts[start_index]]
                start_index += 1
            if end_index < n2 and i > ends[end_index]:
                cut_prefix += d_end[ends[end_index]]
                end_index += 1
            out[i] = prefix - cut_prefix
        return out


data = Solution()
length = 5
updates = [[1, 3, 2], [2, 4, 3], [0, 2, -2]]
print(data.getModifiedArray(length, updates))
